package com.linyaonan.leetcode.medium._LCCI_0202;

/**
 * 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
 * <p>
 * 注意：本题相对原题稍作改动
 * <p>
 * 示例：
 * <p>
 * 输入： 1->2->3->4->5 和 k = 2
 * 输出： 4
 * 说明：
 * <p>
 * 给定的 n 保证是有效的。
 * <p>
 *
 * @author: Lin
 * @date: 2020/2/26
 */
public class KthNode {
    public int kthToLast(ListNode head, int k) {
        ListNode slow = head, fast = head;
        // 快指针先走k步
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        // 快指针走完，慢指针就会剩下k步
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}
